Có nhiều thuật toán khác nhau cho đồ thị có hướng, tùy theo nhu cầu sử dụng chẳng hạn như đỉnh xuất phát hay kết thúc có cố định hay không, và có cần tìm đường cho nhiều cặp đỉnh cùng một lúc hay không.

Mọi cặp đỉnh

Bài toán đường đi rộng nhất giữa mọi cặp đỉnh có ứng dụng trong phương pháp Schulze để xác định người thắng cuộc trong bầu cử với nhiều ứng cử viên trong đó trên mỗi phiếu, các ứng cử viên được xếp hạng theo thứ tự ưu tiên. Phương pháp Schulze xây dựng một đồ thị đấu loại trong đó mỗi đỉnh biểu diễn một ứng cử viên và hai đỉnh bất kì đều được nối với nhau bằng 1 cung. Mỗi cung có hướng từ người thắng cuộc đến người thua cuộc trong cuộc đấu tay đôi giữa hai ứng viên ở hai đầu của cung, và được gắn nhãn bằng chênh lệch giữa hai người. Sau đó, tính đường đi rộng nhất giữa mọi cặp đỉnh của đồ thị và người thắng cuộc là ứng cử viên có đường đi tới mỗi đối thủ rộng hơn đường đi rộng nhất theo hướng ngược lại.[2]. Kết quả của phương pháp này tương thích với phương pháp Condorcet - nếu một ứng cử viên thắng trong tất cả các kết quả so sánh tay đôi thi người đó thắng chung cuộc - nhưng nó cũng cho phép lựa chọn người thắng cuộc trong nhiều trường hợp khi phương pháp Condorcet thất bại.[12] Phương pháp Schulze đã được sử dụng bởi nhiều tổ chức, chẳng hạn như Wikimedia Foundation.[13]

Để tính chiều rộng của đường đi rộng nhất giữa mọi cặp đỉnh trong đồ thị trù mật có hướng, chẳng hạn như đồ thị thu được trong ứng dụng bầu cử, thuật toán nhanh nhất hiện nay chạy trong thời gian O(n(3+ω)/2) trong đó ω là lũy thừa trong thời gian chạy của thuật toán nhân ma trận nhanh. Nếu sử dụng thuật toán nhân ma trận nhanh nhất hiện nay, thì độ phức tạp trên trở thành O(n2.688).[14]Thay vào đó, cách lập trình thông thường của phương pháp Schulze sử dụng một phiên bản của thuật toán Floyd-Warshall chạy trong thời gian O(n3).[2] Trên đồ thị thưa, có thể việc chạy thuật toán tìm đường đi rộng nhất với đỉnh nguồn cố định nhiều lần còn hiệu quả hơn các phương pháp trên.

Một đỉnh nguồn cố định

Nếu độ dài các cạnh đã được sắp xếp thì có thể sử dụng một biến thể của thuật toán Dijkstra để tìm các đường đi rộng nhất từ một đỉnh nguồn cố định tới tất cả các đỉnh khác trong thời gian tuyến tính. Ý tưởng chính ở đây là trong bài toán đường đi rộng nhất, thứ tự các đỉnh được xem xét trong thuật toán chính là một dãy con tăng dần của danh sách các cung sắp xếp theo trọng số. Do đó hàng đợi ưu tiên của thuật toán Dijkstra trong trường hợp này có thể thay bằng một mảng kích thước m lưu trữ các cung của đồ thị theo trọng số tăng dần. Phương pháp này cho phép tìm kiếm đường đi rộng nhất trong thời gian ngang với thời gian sắp xếp. Nếu các trọng số là số nguyên thì thuật toán có cùng thời gian chạy với thuật toán sắp xếp số nguyên.[11]

Một nguồn và một đích

Có thể tìm đường đi rộng nhất cho một đỉnh nguồn và một đỉnh đích duy nhất một cách hiệu quả ngay cả trong mô hình chỉ cho phép so sánh trọng số của các cung mà không được tính toán trên chúng.[11][15] Thuật toán duy trì một tập hợp các cung S sao cho các cung trên đường đi rộng nhất chắc chắn nằm trong S. Ban đầu, S chứa tất cả m cung của đồ thị. Trong mỗi lượt, thuật toán chia tập S thành một danh sách các tập con được sắp thứ tự S1, S2,... (các số trong tập trước nhỏ hơn hoặc bằng các số trong tập sau) có kích thước xấp xỉ nhau. Số lượng tập hợp con được chọn sao cho các giá trị để phân chia S thành các tập con có thể được xác định bằng cách lặp đi lặp lại việc tìm phần tử trung vị trong thời gian O(m). Sau đó, thuật toán thay trọng số của các cung trên đồ thị bằng số thứ tự của tập chứa nó. Do ta đã có danh sách các cung sắp xếp theo trọng số mới, có thể tìm đường đi rộng nhất trong thời gian tuyến tính theo kết quả ở trên và do đó xác định được cung hẹp nhất của đường đi nằm trong tập nào. Sau đó, thuật toán thay tập S bằng tập Si đã được xác định là chứa cung hẹp nhất trên đường, và lặp lại các bước trên. Số lượng tập hợp mà ta có thể chia S tăng theo hàm mũ sau mỗi lần lặp nên số lần lặp là O(log*n). Tổng thời gian, do đó, là O(m log*n).[15] Khi các trọng số là số nguyên, bước lặp đi lặp lại việc tìm kiếm trung vị có thể thay bằng kĩ thuật phân chia danh sách bởi Han & Thorup (2002)Lỗi harv: không có mục tiêu: CITEREFHanThorup2002 (trợ giúp), cho phép chia S thành O ( m ) {\displaystyle O({\sqrt {m}})} tập con Si trong một bước và toàn bộ thuật toán chạy trong thời gian tuyến tính.[16]